package com.tgy.dynamic.programming;

/**
 * @Author: tgy
 * @Date: 2020-11-16 16:22
 * longest increasing subsequence
 */
public class LIS01 {

    /**
     * 使用二分查找，时间复杂度变成 O(n*log(n))
     * @param arr
     * @return
     */
    public int lis(int[] arr) {

        int[] tops = new int[arr.length];

        int len = 0;
        for (int val : arr) {

            int mid,left = 0, right = len;
            while (left != right) {

                mid = (left + right) >> 1;

                if (val > arr[mid]) {

                    left = mid + 1;
                }else {
                    // val <= arr[mid] 时不断设置 right靠近 left。
                    right = mid;
                }
            }

            arr[left] = val;
            if (left == len) {
                len++;
            }
        }

        return len;
    }


    /**
     * 时间复杂度为 o(n^2)
     * @param arr
     * @return
     */
//    public int lis01(int[] arr) {
//
//        int[] tops = new int[arr.length];
//
//        int len = 0;
//        for (int val : arr) {
//            int j = 0;
//            for (; j < len; j++) {
//
//                if (tops[j] >= val) {
//
//                    break;
//                }
//            }
//
//            if (j == len) {
//
//                tops[len++] = val;
//            }else {
//
//                tops[j] = val;
//            }
//
//        }
//
//        return len;
//    }
}
